package com.example.hashtable;

/**
 * 给定一个字符串s，请你找出其中不含有重复字符的 最长子串 的长度
 * s 由英文字母、数字、符号和空格组成
 * <p>
 * 输入: s = "abcabcbb"
 * 输出: 3
 * <p>
 * 输入: s = "bbbbb"
 * 输出: 1
 * <p>
 * 输入: s = "pwwkew"
 * 输出: 3
 */
public class Leetcode3_LengthOfLongestSubstring {
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring2("abcabcbb"));
    }

    /**
     * 解法一:暴力解法
     * <p>
     * 双指针截取所有无重复字符的子串，返回最长的子串的长度
     *
     * @param s s 由英文字母、数字、符号和空格组成
     * @return
     */
    public static int lengthOfLongestSubstring1(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int maxSubstringLen = 1;

        for (int start = 0; start < s.length(); start++) {
            for (int end = start + 1; end < s.length(); end++) {
                String substring = s.substring(start, end);
                if (substring.indexOf(s.charAt(end)) != -1) { // 说明索引为end的字符在所截取的子串中存在
                    break;
                }
                maxSubstringLen = (end - start + 1) > maxSubstringLen ?
                        (end - start + 1) : maxSubstringLen;
            }
        }
        return maxSubstringLen;
    }

    /**
     * 解法二:双指针+hash表(最优解)
     * <p>
     * 思路：
     * 遍历字符串的所有字符，使用双指针定位不重复子串的起止索引，
     * 并将字符临时记录到哈希表中，每次计算子串的长度并统计最大值
     * <p>
     * 步骤：
     * 1.定义哈希表，临时存储子串字符和查重
     * 定义哈希函数，对任意字符生成唯一整数值
     * 2.遍历字符串，通过双指针循环定位子串
     * 右指针在哈希表中是否存在：
     * 否，记录到哈希表，移动右指针，计算长度；
     * 是，删除哈希表中左指针元素，移动左指针，重复检查右指针元素是否还存在；
     * 3.每次计算子串长度，比较并保留最大值
     * <p>
     * 边界问题
     * 遍历字符串的字符，注意索引越界
     * 计算子串长度时，注意子串的起止索引
     * 根据测试用例，子串长度不会超过哈希表容量：new char[128]
     * 细节问题
     * 子串长度是：right + 1 - left
     * 出现重复元素后，左指针逐个移动，直到与当前重复的字符索引+1
     *
     * @return
     */
    public static int lengthOfLongestSubstring2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        // 1.定义哈希表，支持ASCII码表的全部字符
        // 该hashTable，要按照字符ASCII码 为索引存放对应的字符
        // 即 hashTable[97] = 'a' 依次类推
        char[] hashTable = new char[128];
        int maxSubstringLen = 0;
        int left = 0, right = 0;

        //2.遍历字符串，通过双指针循环定位子串
        while (right < s.length()) {
            char rightChar = s.charAt(right);
            // 求出右指针指向的字符在hashTable中的索引
            int index = hash(rightChar) & (hashTable.length - 1); // x & 2^n -1  <=> x % 2^n
            // 判断当前子串（left~right）有没有重复的元素 ：右指针指向的字符是否在hashTable中存在
            if (hashTable[index] != rightChar) { // 不等，当前子串没有重复元素
                // 将右指针指向的字符加入到hashtable中，更新最长不重复子串长度，最后将右指针右移
                hashTable[index] = rightChar;
                // 更新最长不重复子串长度
                maxSubstringLen = (right - left + 1) > maxSubstringLen
                        ? (right - left + 1) : maxSubstringLen;
                right++;
            } else {// 相等，说明右指针指向的字符已经在子串出现过
                // 删除哈希表中左指针元素，移动左指针
                char leftChar = s.charAt(left++);
                hashTable[hash(leftChar) & (hashTable.length - 1)] = '\u0000';
            }
        }
        return maxSubstringLen;
    }

    /**
     * 哈希函数，对任意字符生成唯一整数值(直接返回字符对应的ASCII码)
     * 这个整数值用于从hash表中通过除留余数来访问数据
     *
     * @param c
     * @return
     */
    public static int hash(char c) {
        return c;
    }

    /**
     * 最优解：哈希表 + 双指针优化思路
     * 1.哈希表作用变形
     * 由 字符ASCII码值 --> 字符
     * 变为字符ASCII码值 --> 字符最后出现索引
     * 2.遇到重复元素后，左指针移动优化
     * 逐个移动到前一个相同字符出现后的位置 -->
     * 一次性定位到前一个相同字符出现后的位置
     * <p>
     * 步骤：
     * 1.初始化哈希表，存入非ASCII码值作为默认值
     * 2.遍历字符串，使用双指针定位子串索引
     * 字符已出现：取出哈希表中记录，左指针到记录+1
     * 无论是否出现，将右指针记录到哈希表
     * 3.每次移动都记录子串长度，保留最大值
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        int len; // 源字符串长度
        if (s == null || (len = s.length()) == 0) {
            return 0;
        }
        int res = 0, // 最长不重复子串的长度
                left = 0, // 子串最左端字符索引
                right = 0; // 子串最右端字符索引
        // 1.哈希表中填充ASCII码表不包含的数值作为默认值：-1
        int[] arr = new int[128]; // ASCII码 --> 最后一次出现的索引
        for (int i = 0; i < arr.length; i++)
            arr[i] = -1;
        // 2.遍历字符串的所有字符
        while (right < len) { // abba
            int c = s.charAt(right);
            if (arr[c] != -1) { // 检测该字符是否已经出现：已出现
                // 出现，则移动左指针，直接定位到上次出现的下一个索引
                int start0 = arr[c] + 1;
                // 2.1.使用双指针定位子串索引：左指针直接定位
                left = left >= start0 ? left : start0; // 只往右不往左
            }
            // 无论是否重复，记录该字符最后一次出现的索引
            arr[c] = right; // ASCII码值 ： 字符最后出现的索引
            // 3.计算子串长度，记录最大值：右索引+1 - 左索引
            int size = right + 1 - left;
            res = res > size ? res : size;
            // 2.2.使用双指针定位子串索引：右指针始终自增
            right++;
        }
        return res;
    }
}
